package util;

import graph.Graph;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Path<V, E extends Graph.Edge<V>> {

    private Map<V, Boolean> marked;
    private Map<V, V> edgeTo;
    private Map<V, Integer> distance;
    private V root;

    public Path(Graph<V, E> graph, V s) {
        edgeTo = new HashMap<V, V>();
        distance = new HashMap<V, Integer>();
        marked = new HashMap<V, Boolean>();
        root = s;
        for (V v : graph.vertices()) {
            marked.put(v, false);
        }
        distance.put(root, 0);
        dfs(graph, root);
    }

    public boolean hasPathTo(V v) {
        return edgeTo.containsKey(v);
    }

    public int distanceTo(V v) {
        return distance.get(v);
    }

    public ArrayList<V> pathTo(V v) {
        if (!hasPathTo(v)) {
            return null;
        }
        ArrayList<V> path = new ArrayList<V>();
        V x = v;
        while (x != root) {
            path.add(x);
            x = edgeTo.get(x);
        }
        path.add(root);
        return path;
    }

    private void dfs(Graph<V, E> graph, V v) {
        marked.put(v, true);
        for (V w : graph.neighbors(v)) {
            if (!marked.get(w)) {
                edgeTo.put(w, v);
                distance.put(w, distance.get(v) + 1);
                dfs(graph, w);
            }
        }
    }
}
